package xyz.zhuht.algorithm.difficult;

/**
 * @author haitao zhu
 * @date 2020/7/18 22:24
 * 97.交错字符串
 * <p>
 * 给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
 * <p>
 * 示例 1:
 * <p>
 * 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
 * 输出: true
 * 示例 2:
 * <p>
 * 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
 * 输出: false
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/interleaving-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class JiaoCuoZiFuChuan {
  public boolean isInterleave(String s1, String s2, String s3) {
    int n = s1.length(), m = s2.length(), t = s3.length();

    if (n + m != t) {
      return false;
    }

    boolean[] f = new boolean[m + 1];

    f[0] = true;
    for (int i = 0; i <= n; ++i) {
      for (int j = 0; j <= m; ++j) {
        int p = i + j - 1;
        if (i > 0) {
          f[j] = f[j] && s1.charAt(i - 1) == s3.charAt(p);
        }
        if (j > 0) {
          f[j] = f[j] || (f[j - 1] && s2.charAt(j - 1) == s3.charAt(p));
        }
      }
    }

    return f[m];
  }

}
